package leetcode_21_40;

public class strStr_28 {
    public static int strStr(String haystack, String needle) {
        int h_len = haystack.length(), n_len = needle.length();
        for (int i = 0; i < h_len - n_len + 1; i++) {                        //最多只需要匹配到倒数第n_len个字符即可
            if (haystack.charAt(i) == needle.charAt(0)) {                 //比较字符是否与needle的第一个字符相同
                int t = 1;
                for (; t < n_len; t++) {                                                     //从后一位开始逐个比较
                    if (haystack.charAt(i + t) != needle.charAt(t)) {  //有一位不相等就退出
                        break;
                    }
                }
                if (t == n_len) {                       //全部对应则返回此时的下标
                    return i;
                }
            }
        }
        return -1;
    }


    /**
     * 得到字符串的PM数组
     * 经过处理（首位补负一，整体加一，向右移动一位）
     */
    public void getNext(int[] next, String s) {
        int pre = 0, i = 1;  // pre 前缀长度
        next[0] = 0;
        while (i < s.length()) {
            if (s.charAt(i) == s.charAt(pre)) { //前后缀末尾相同
                pre++;
                next[i] = pre;
                i++;
            } else {
                if (pre == 0) {
                    next[i] = 0;
                    i++;
                } else
                    pre = next[pre - 1];
                //遇到前后缀末尾不相同的情况， pre 就回退到前面字符串匹配到的前后缀长度
                //如  0   1   2   3   4    5   6   7
                //      a   b   a   c    a   b   a   b
                //      0   0   1   0    1   2   3   2
                //匹配 b 和 f 时 ，不匹配,  pre 为 3，i为 7
                //我们需要知道4位长的前后缀不匹配，那么其次还有可能多长，于是去找前面 匹配到的 a b a 尾部 和 与其对应的 a b a的头部 能匹配多少
                //可以跳过匹配的长度继续匹配，这个长度在前面计算next数组时已经知道了就是 next[2] = 1 ，跳过一个位置即0，在 1 处继续匹配
            }
        }
    }

    public int strStr2(String haystack, String needle) {
        if (needle.length() == 0)
            return 0;
        int[] next = new int[needle.length()];
        getNext(next, needle);
        int j = 0;
        for (int i = 0; i < haystack.length(); i++) {
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = next[j - 1];  //回退到前面字符串匹配到的前后缀长度
            }
            if (haystack.charAt(i) == needle.charAt(j)) {
                j++;
            }
            if (j == needle.length()) {
                return (i - needle.length() + 1);
            }
        }
        return -1;
    }


}
